//3171. 找到按位或最接近 K 的子数组

//给你一个数组 nums 和一个整数 k 。你需要找到 nums 的一个 子数组 ，满足子数组中所有元素按位或运算 OR 的值与 k 的 绝对差 尽可能 小 。
//换言之，你需要选择一个子数组 nums[l..r] 满足 | k - (nums[l] OR nums[l + 1] ... OR nums[r]) | 最小。
//请你返回 最小 的绝对差值。
//子数组 是数组中连续的 非空 元素序列。

//class Solution {
//public:
//    int minimumDifference(vector<int>& nums, int k) {
//        int ans = INT_MAX;
//        for (int i = 0; i < nums.size(); i++) {
//            int x = nums[i];
//            ans = min(ans, abs(x - k));
//            //如果 x 是 nums[j] 的子集，退出循环
//            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
//                nums[j] |= x;
//                ans = min(ans, abs(nums[j] - k));
//            }
//        }
//        return ans;
//    }
//};

//1521. 找到最接近目标值的函数值

//Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ，他想找到让 | func(arr, l, r) - target | 最小的 l 和 r 。
//请你返回 | func(arr, l, r) - target | 的最小值。
//请注意， func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。

//class Solution {
//public:
//    int closestToTarget(vector<int>& arr, int k) {
//        int ans = 0x3f3f3f3f, n = arr.size();
//        for (int i = 0; i < n; i++) {
//            int x = arr[i];
//            ans = min(ans, abs(x - k));
//            for (int j = i - 1; j >= 0 && (arr[j] & x) != arr[j]; j--) {
//                arr[j] &= x;
//                ans = min(ans, abs(arr[j] - k));
//            }
//        }
//        return ans;
//    }
//};

//3097. 或值至少为 K 的最短子数组 II

//给你一个 非负 整数数组 nums 和一个整数 k 。
//如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。
//请你返回 nums 中 最短特别非空 子数组的长度，如果特别子数组不存在，那么返回 - 1 。

//class Solution {
//public:
//    int minimumSubarrayLength(vector<int>& nums, int k) {
//        int ans = 0x3f3f3f3f, n = nums.size();//0x3f3f3f3f对于10e9足够
//        for (int i = 0; i < n; i++) {
//            int x = nums[i];
//            if (x >= k) {
//                return 1;
//            }
//            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
//                nums[j] |= x;
//                if (nums[j] >= k) {
//                    ans = min(ans, i - j + 1);
//                }
//            }
//        }
//        return ans == 0x3f3f3f3f ? -1 : ans;
//    }
//};

//2411. 按位或最大的最小子数组长度

//给你一个长度为 n 下标从 0 开始的数组 nums ，数组中所有数字均为非负整数。对于 0 到 n - 1 之间的每一个下标 i ，
//你需要找出 nums 中一个 最小 非空子数组，它的起始位置为 i （包含这个位置），同时有 最大 的 按位或运算值 。
//换言之，令 Bij 表示子数组 nums[i...j] 的按位或运算的结果，你需要找到一个起始位置为 i 的最小子数组，这个子数组的按位或运算的结果等于 max(Bik) ，其中 i <= k <= n - 1 。
//一个数组的按位或运算值是这个数组里所有数字按位或运算的结果。
//请你返回一个大小为 n 的整数数组 answer，其中 answer[i]是开始位置为 i ，按位或运算结果最大，且 最短 子数组的长度。
//子数组 是数组里一段连续非空元素组成的序列。

//class Solution {
//public:
//    vector<int> smallestSubarrays(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> ans(n, 1);
//        for (int i = 0; i < n; i++) {
//            int x = nums[i];
//            for (int j = i - 1; j >= 0 && (nums[j] | x) != nums[j]; j--) {
//                nums[j] |= x;
//                ans[j] = i - j + 1;
//            }
//        }
//        return ans;
//    }
//};

//3209. 子数组按位与值为 K 的数目

//给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中有多少个子数组满足：子数组中所有元素按位 AND 的结果为 k

//class Solution {
//public:
//    long long countSubarrays(vector<int>& nums, int k) {
//        long long ans = 0;
//        int cnt = 0, n = nums.size();
//        for (int i = 0; i < n; i++) {
//            int x = nums[i];
//            cnt += x == k;
//            for (int j = i - 1; j >= 0 && (nums[j] & x) != nums[j]; j--) {
//                cnt -= nums[j] == k;
//                nums[j] &= x;
//                cnt += nums[j] == k;
//            }
//            ans += cnt;
//        }
//        return ans;
//    }
//};

//898. 子数组按位或操作

//给定一个整数数组 arr，返回所有 arr 的非空子数组的不同按位或的数量。
//子数组的按位或是子数组中每个整数的按位或。含有一个整数的子数组的按位或就是该整数。
//子数组 是数组内连续的非空元素序列。

//class Solution {
//public:
//    int subarrayBitwiseORs(vector<int>& arr) {
//        unordered_set<int> st;
//        for (int i = 0; i < arr.size(); i++) {
//            st.insert(arr[i]);
//            for (int j = i - 1; j >= 0 && (arr[j] | arr[i]) != arr[j]; j--) {
//                arr[j] |= arr[i];
//                st.insert(arr[j]);
//            }
//        }
//        return st.size();
//    }
//};